#include <stdio.h>

int print_wv(float w[], float v[], int n);
int sort_forwv(float w[], float v[], int n);  // 按单价递减排序
int greedy_bag(float w[], float v[], float capacity, int n);

int main(int argc, const char** args) {
	float w[] = {1 , 3 , 2 , 4 , 5};
	float v[] = {3 , 3 , 4 , 1 , 4};
	float capacity = 10;
	int n = sizeof(w) / sizeof(float);

	printf("\n==========NORMAL_WV===========\n");
	print_wv(w, v, n);

	sort_forwv(w, v, n);

	printf("\n\n=========SORTED_WV==========\n");
	print_wv(w, v, n);
	printf("\ncapacity: %.2f\n", capacity);

	greedy_bag(w, v, capacity, n);

	return 0;
}

int print_wv(float w[], float v[], int n) {
	int i, j;

	printf("w[]: ");
	for (i = 0; i < n; ++i) {
		printf("%.2f ", w[i]);
	}
	printf("\nv[]: ");
	for (i = 0; i < n; ++i) {
		printf("%.2f ", v[i]);
	}

	return 0;
}

int sort_forwv(float w[], float v[], int n) {
	int i, j;
	int max;
	int temp;
	for (i = 0; i < n; ++i) {
		max = i;
		for (j = i + 1; j < n; ++j) {
			if (v[max] / w[max] < v[j] / w[j]) {
				max = j;
			}
		}
		temp = w[i];
		w[i] = w[max];
		w[max] = temp;

		temp = v[i];
		v[i] = v[max];
		v[max] = temp;
	}

	return 0;
}

int greedy_bag(float w[], float v[], float capacity, int n) {
	int i;
	float sum = 0;
	for (i = 0; i < n; ++i) {
		if (w[i] < capacity) {
			sum += v[i];
			capacity -= w[i];
		}
		else {
			sum += capacity / w[i] * v[i];
			break;
		}
	}
	printf("\nresult: %.2f\n", sum);

	return 0;
}